package com.klun.project.common.constans.leetcode;
//给定一个有序整数数组，元素各不相同且按升序排列，
// 编写一个算法，创建一棵高度最小的二叉搜索树。示例: 给定有序数组: [-10,-3,0,5,9], 一个可能
//的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：           0          / \        -3
//  9        /   /      -10  5 Related Topics 树 二叉搜索树 数组 分治 二叉树
// 👍 139 👎 0

import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

public class Solution0402 {

	public TreeNode sortedArrayToBST(int[] nums) {
		return dfs(0, nums.length - 1, nums);
	}

	public TreeNode dfs(int l, int r, int[] nums) {
		if (l > r) return null;
		int mid = (l + r) / 2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = dfs(l, mid - 1, nums);
		root.right = dfs(mid + 1, r, nums);
		return root;
	}

	public static void main(String[] args) {
		Solution0402 solution = new Solution0402();
//		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
		TreeNode treeNode = ParseUtils.ArrayToBTree("[-10,-3,0,5,9]");
		ParseUtils.stringToArrayInt("[-10,-3,0,5,9]");
		TreeNode treeNode1 = solution.sortedArrayToBST(new int[]{-10, -3, 0, 5, 9});
		System.out.println(treeNode1);
	}
}
